from ..errors import LRUError

# 理论上，当前数据库的内存使用，大约就应该是：
# PAGE_SIZE * LRU_CAPACITY + 小部分其他开销 = 数据库进程总使用内存
# innodb_buffer_pool_size 
LRU_CAPACITY = 100

class LRUNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value # 在LRU中就是page
        self.prev = None
        self.next = None

        # 额外字段
        self.pinned = False # 是否被锁定(标记节点是否正在被使用)，不能被淘汰
    
    def __repr__(self):
        return f"LRUNode(key={self.key}, value={self.value}, pinned={self.pinned})"

# TODO: 当前LRU实现，没有考虑并发问题, 后续需要考虑, 比如并发读写
class LRUCache:
    def __init__(self, capacity=LRU_CAPACITY):
        self.capacity = capacity
        self.cache = {}
        # 小优化：先把被淘汰的数据暂存到这里 evicted
        self.evicted = []

        # LRU中的链表，这里边实现的是双向链表
        # 使用 dummy node 技巧：可以帮我们少些很多边界条件的判断
        self.head = LRUNode(None, None)
        self.tail = LRUNode(None, None)

        self.head.next = self.tail
        self.tail.prev = self.head



    def put(self, key, value):
        if key in self.cache:
            # 此时，相当于访问lru中已经存在的一个节点
            # 需要把这个节点提取到最前面的位置
            node = self.cache[key]
            self._remove(node)

        node = LRUNode(key, value)
        self.cache[key] = node
        self._add(node)

        # 开始进行淘汰判断，即超过capacity上限，需要从头部head进行剔除
        if len(self.cache) > self.capacity:
            # 大于就要进行淘汰
            evictd_node = self.head.next
            while evictd_node and evictd_node.pinned:
                evictd_node = evictd_node.next

            if evictd_node is self.tail:
                # 删除刚刚插入的新node，同时报错
                self._remove(node)
                del self.cache[key]
                raise LRUError('no avaliable space for current node.')
            
            self._remove(evictd_node)
            del self.cache[evictd_node.key]
            self.evicted.append(evictd_node)
            
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            # 下面一个删除 + 一个添加，相当于把节点提取到链表头部
            self._remove(node)
            self._add(node)
            return node.value

        return None

    def _add(self, node: LRUNode):
        # 添加节点到链表头部
        # 新节点从尾部进行插入，旧节点从头部剔除
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail

        self.tail.prev = node

    @staticmethod
    def _remove(node: LRUNode):
        # 删除节点
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev

    def pin(self, key):
        if key not in self.cache:
            raise LRUError(f'not found key: {key}')

        self.cache[key].pinned = True

    def unpin(self, key):
        if key not in self.cache:
            raise LRUError(f'not found key: {key}')

        self.cache[key].pinned = False

    def items(self):
        # 遍历当前LRU中的所有元素
        node = self.head.next
        while node != self.tail:
            yield node.key, node.value
            node = node.next